<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <meta name="author" content="Mouse0w0">
  
  <link rel="shortcut icon" href="../img/favicon.ico">
  <title>优化 - 截锥剔除 - Lwjglbook中文翻译</title>
  <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Lato:400,700|Roboto+Slab:400,700|Inconsolata:400,700" />

  <link rel="stylesheet" href="../css/theme.css" />
  <link rel="stylesheet" href="../css/theme_extra.css" />
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/styles/github.min.css" />
  
  <script>
    // Current page data
    var mkdocs_page_name = "\u4f18\u5316 - \u622a\u9525\u5254\u9664";
    var mkdocs_page_input_path = "25-optimizations-frustum-culling.md";
    var mkdocs_page_url = null;
  </script>
  
  <script src="../js/jquery-2.1.1.min.js" defer></script>
  <script src="../js/modernizr-2.8.3.min.js" defer></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/highlight.min.js"></script>
  <script>hljs.initHighlightingOnLoad();</script> 
  
</head>

<body class="wy-body-for-nav" role="document">

  <div class="wy-grid-for-nav">

    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side stickynav">
    <div class="wy-side-scroll">
      <div class="wy-side-nav-search">
        <a href=".." class="icon icon-home"> Lwjglbook中文翻译</a>
        <div role="search">
  <form id ="rtd-search-form" class="wy-form" action="../search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" title="Type search term here" />
  </form>
</div>
      </div>

      <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../01-first-steps/">事前准备</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../02-the-game-loop/">游戏循环</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../03-a-brief-about-coordinates/">坐标简介</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../04-rendering/">渲染</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../05-more-on-rendering/">渲染补充</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../06-transformations/">变换</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../07-textures/">纹理</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../08-camera/">摄像机</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../09-loading-more-complex-models/">加载更复杂的模型</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../10-let-there-be-light/">要有光</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../11-let-there-be-even-more-light/">要有更多的光</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../12-game-hud/">游戏HUD</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../13-sky-box-and-some-optimizations/">天空盒与一些优化</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../14-height-maps/">高度图</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../15-terrain-collisions/">地形碰撞</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../16-fog/">雾</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../17-normal-mapping/">法线贴图</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../18-shadows/">阴影</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../19-animations/">动画</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../20-particles/">粒子</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../21-instanced-rendering/">实例化渲染</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../22-audio/">音效</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../23-3d-object-picking/">三维物体选取</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../24-hud-revisited/">回顾HUD - NanoVG</a>
                    </li>
                </ul>
                <ul class="current">
                    <li class="toctree-l1 current"><a class="reference internal current" href="./">优化 - 截锥剔除</a>
    <ul class="current">
    <li class="toctree-l2"><a class="reference internal" href="#-">优化 - 截锥剔除一</a>
    </li>
    </ul>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../26-cascaded-shadow-maps/">级联阴影映射</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../27-assimp/">Assimp库</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../28-deferred-shading/">延迟着色法</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../a01-opengl-debugging/">附录 A - OpenGL调试</a>
                    </li>
                </ul>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../glossary/">术语表</a>
                    </li>
                </ul>
      </div>
    </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" role="navigation" aria-label="top navigation">
        <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
        <a href="..">Lwjglbook中文翻译</a>
      </nav>

      
      <div class="wy-nav-content">
        <div class="rst-content">
          <div role="navigation" aria-label="breadcrumbs navigation">
  <ul class="wy-breadcrumbs">
    <li><a href="..">Docs</a> &raquo;</li>
    
      
    
    <li>优化 - 截锥剔除</li>
    <li class="wy-breadcrumbs-aside">
      
        <a href="https://github.com/Mouse0w0/lwjglbook-CN-Translation/edit/master/docs/25-optimizations-frustum-culling.md"
          class="icon icon-github"> Edit on GitHub</a>
      
    </li>
  </ul>
  
  <hr/>
</div>
          <div role="main">
            <div class="section">
              
                <h1 id="-optimizations-frustum-culling">优化 - 截锥剔除（Optimizations - Frustum Culling）</h1>
<h2 id="-">优化 - 截锥剔除一</h2>
<p>现在我们使用了许多不同的图形效果，例如光照、粒子等。此外，我们还学习了如何实例化渲染，以减少绘制许多相似对象的开销。然而，我们仍有足够的空间进行一些简单的优化，这将增加可以达到的帧率（FPS）。</p>
<p>你可能想知道为什么我们会在每一帧中绘制整个游戏项列表，即使其中一些项不可见（因为它们在摄像机后面或距离摄像机太远）。你甚至可能认为这是由OpenGL自动处理的，这在某种程度上是正确的。OpenGL将放弃位于可见区域之外的顶点的渲染，这称作裁剪（Clipping）。裁剪的问题是，在执行顶点着色之后，按顶点进行处理的。因此，即使此操作节省了资源，我们也可以通过不尝试渲染不可见的对象来提高效率。我们不会通过将数据发送到GPU以及对这些对象的每个顶点进行变换来浪费资源。我们需要移除不包含在视锥体（View Frustum）中的对象，也就是说，我们需要进行截锥剔除。</p>
<p>但是，首先让我们回顾一下什么是视锥体。视锥体是一个结合摄像机的位置和旋转以及使用的投影，包含所有可见物体的体积。通常，视锥体是一个四棱台，如下图所示：</p>
<p><img alt="视锥体I" src="../_static/25/view_frustum_i.png" /></p>
<p>如你所见，视锥体由六个平面定义，位于视锥体之外的任何内容都不会渲染。因此，截锥剔除是移除视锥体之外的对象的过程。</p>
<p>因此，为了进行截锥剔除，我们需要：</p>
<ul>
<li>
<p>使用观察和投影矩阵中包含的数据计算截锥平面。</p>
</li>
<li>
<p>对每个游戏项检查它是否包含在视锥体中，换句话说，在大小截锥平面之间。并从渲染流程中删除那些不包含在其中的。</p>
</li>
</ul>
<p><img alt="视锥体II" src="../_static/25/view_frustum_ii.png" /></p>
<p>那么让我们从计算截锥平面开始。平面由包含在其中的点和与该平面正交的向量定义，如下图所示：</p>
<p><img alt="平面" src="../_static/25/plane.png" /></p>
<p>平面方程的定义如下：</p>
<p>
<script type="math/tex; mode=display">Ax+By+Cz+D=0</script>
</p>
<p>因此，我们需要计算视锥体的六个侧面的六个平面方程。为了达成这个目标，你基本上有两个选项。你可以进行繁琐的计算，得到六个平面方程的来自上述方程的四个常数（A、B、C和D）。另一个选项是让<a href="https://github.com/JOML-CI/JOML" title="JOML">JOML</a>库为你计算这个值。通常情况下，我们选择后一个选项。</p>
<p>让我们开始编码吧。我们将创建一个名为<code>FrustumCullingFilter</code>的新类，跟它的名字相同，它将根据视锥体执行筛选操作。</p>
<pre><code class="java">public class FrustumCullingFilter {

    private static final int NUM_PLANES = 6;

    private final Matrix4f prjViewMatrix;

    private final Vector4f[] frustumPlanes;

    public FrustumCullingFilter() {
        prjViewMatrix = new Matrix4f();
        frustumPlanes = new Vector4f[NUM_PLANES];
        for (int i = 0; i &lt; NUM_PLANES; i++) {
            frustumPlanes[i] = new Vector4f();
        }
    }
</code></pre>

<p><code>FrustumCullingFilter</code>类也将有一个方法来计算平面方程，名为<code>updateFrustum</code>，它将在渲染之前调用。方法定义如下：</p>
<pre><code class="java">public void updateFrustum(Matrix4f projMatrix, Matrix4f viewMatrix) {
    // 计算投影观察矩阵
    prjViewMatrix.set(projMatrix);
    prjViewMatrix.mul(viewMatrix);
    // 获取视锥体平面
    for (int i = 0; i &lt; NUM_PLANES; i++) {
        prjViewMatrix.frustumPlane(i, frustumPlanes[i]);
    }
}
</code></pre>

<p>首先，我们储存投影矩阵的副本，并将其与观察矩阵相乘，得到投影观察矩阵。然后，使用这个变换矩阵，我们只需要为每个截锥平面调用<code>frustumPlane</code>方法。需要注意的是，这些平面方程是用世界坐标表示的，所以所有的计算都要在这个空间中进行。</p>
<p>现在我们已经计算了所有平面，我们只需要检查<code>GameItem</code>实例是否在截锥体中。该怎么做？让我们首先确认一下如何检查一个点是否在截锥体内，可以通过计算点到每个平面的有符号的距离来实现这一点。如果点到平面的距离是正的，这意味着点在平面的前面（根据其法线）。如果是负的，则意味着点在平面的后面。</p>
<p><img alt="到平面的距离" src="../_static/25/distance_to_plane.png" /></p>
<p>因此，如果到截锥的所有平面的距离为正，则一个点位于视锥体的内部。点到平面的距离定义如下：</p>
<p>
<script type="math/tex">距离=Ax_{0}+By_{0}+Cz_{0}+D</script>，其中<script type="math/tex">x_{0}</script>、<script type="math/tex">y_{0}</script>和<script type="math/tex">z_{0}</script>是点的坐标。</p>
<p>因此，如果<script type="math/tex">Ax_{0}+By_{0}+Cz_{0}+D <= 0</script>则点在平面的后面。</p>
<p>但是，我们没有点，只有复杂的网格，我们不能仅仅用点来检查一个物品是否在截锥体内。你可以考虑检查<code>GameItem</code>的每个顶点，看看它是否在截锥体内。如果任何一个点在里面，游戏项应该被绘制出来。但这就是OpenGL在裁剪时所做的，也是我们要避免的。记住，网格越复杂，截锥剔除的好处越明显。</p>
<p>我们需要把每一个<code>GameItem</code>放到一个简单的体中，这个体很容易检查。这里我们有两个选项：</p>
<ul>
<li>
<p>边界盒（Bounding Box）。</p>
</li>
<li>
<p>边界球（Bounding Sphere）。</p>
</li>
</ul>
<p>在本例中，我们将使用球体，因为这是最简单的方法。我们将把每一个游戏项放在一个球体中，并检查球体是否位于视锥体中。为了做到它，我们只需要球体的中心和半径。检查它几乎等同于检查点，但是我们需要考虑板甲。如果满足以下条件，则球体将位于截锥之外：<script type="math/tex">距离=Ax_{0}+By_{0}+Cz_{0} <= -半径</script>。</p>
<p><img alt="边界球" src="../_static/25/bounding_sphere.png" /></p>
<p>因此，我们将在<code>FrustumCullingFilter</code>类中添加一个新方法来检查球体是否在截锥中。方法的定义如下：</p>
<pre><code class="java">public boolean insideFrustum(float x0, float y0, float z0, float boundingRadius) {
    boolean result = true;
    for (int i = 0; i &lt; NUM_PLANES; i++) {
        Vector4f plane = frustumPlanes[i];
        if (plane.x * x0 + plane.y * y0 + plane.z * z0 + plane.w &lt;= -boundingRadius) {
            result = false; return result;
        }
    }
    return result;
}
</code></pre>

<p>然后，我们将添加过滤视锥体外的游戏项的方法：</p>
<pre><code class="java">public void filter(List&lt;GameItem&gt; gameItems, float meshBoundingRadius) {
    float boundingRadius;
    Vector3f pos;
    for (GameItem gameItem : gameItems) {
        boundingRadius = gameItem.getScale() * meshBoundingRadius;
        pos = gameItem.getPosition();
        gameItem.setInsideFrustum(insideFrustum(pos.x, pos.y, pos.z, boundingRadius));
    }
}
</code></pre>

<p>我们在<code>GameItem</code>类中添加了一个新的属性<code>insideFrustum</code>来跟踪可见性。如你所见，边界球的板甲作为参数传递。这是由于边界球与<code>Mesh</code>管理，它不是<code>GameItem</code>的属性。但是，请记住，我们必须在世界坐标中操作，并且边界球的半径将在模型空间震。我们将应用为<code>GameItem</code>设置的比例将其转换为世界空间，我们还假设<code>GameItem</code>的位置是球体的中心（在世界空间坐标系中）。</p>
<p>最后一个方法只是一个实用方法，它接受网格表并过滤其中包含的所有<code>GameItem</code>实例：</p>
<pre><code class="java">public void filter(Map&lt;? extends Mesh, List&lt;GameItem&gt;&gt; mapMesh) {
    for (Map.Entry&lt;? extends Mesh, List&lt;GameItem&gt;&gt; entry : mapMesh.entrySet()) {
        List&lt;GameItem&gt; gameItems = entry.getValue();
        filter(gameItems, entry.getKey().getBoundingRadius());
    }
}
</code></pre>

<p>就这样。我们可以在渲染流程中使用该类，只需要更新截锥平面，计算出哪些游戏项是可见的，并在绘制实例网格和非实例网格时过滤掉它们：</p>
<pre><code class="java">frustumFilter.updateFrustum(window.getProjectionMatrix(), camera.getViewMatrix());
frustumFilter.filter(scene.getGameMeshes());
frustumFilter.filter(scene.getGameInstancedMeshes());
</code></pre>

<p>你可以启用或禁用过滤功能，并可以检查你可以达到的FPS的增加和减少。在过滤时不考虑粒子，但是添加它是很简单的。对于粒子，在任何情况下最好检查发射器的位置，而不是检查每个粒子。</p>
<h1 id="-_1">优化 - 截锥剔除二</h1>
<p>解释了截锥剔除的基础，我们可以使用<a href="https://github.com/JOML-CI/JOML" title="JOML">JOML</a>库中提供的更精细的方法。它特别地提供了一个名为<code>FrustumIntersection</code>的类，该类以按此<a href="http://gamedevs.org/uploads/fast-extraction-viewing-frustum-planes-from-world-view-projection-matrix.pdf" title="paper">文章</a>所述的一种更有效的方式获取视锥体的平面。除此之外，该类还提供了测试边界盒、点和球体的方法。</p>
<p>那么，让我们修改<code>FrustumCullingFilter</code>类。属性和构造函数简化如下：</p>
<pre><code class="java">public class FrustumCullingFilter {

    private final Matrix4f prjViewMatrix;

    private FrustumIntersection frustumInt;

    public FrustumCullingFilter() {
        prjViewMatrix = new Matrix4f();
        frustumInt = new FrustumIntersection();
    }
</code></pre>

<p><code>updateFrustum</code>方法只是将平面获取委托给<code>FrustumIntersection</code>实例：</p>
<pre><code class="java">public void updateFrustum(Matrix4f projMatrix, Matrix4f viewMatrix) {
    // 计算投影识图矩阵
    prjViewMatrix.set(projMatrix);
    prjViewMatrix.mul(viewMatrix);
    // 更新截锥相交类
    frustumInt.set(prjViewMatrix);
}
</code></pre>

<p><code>insideFrustum</code>方法更简单：</p>
<pre><code class="java">public boolean insideFrustum(float x0, float y0, float z0, float boundingRadius) {
    return frustumInt.testSphere(x0, y0, z0, boundingRadius);
}
</code></pre>

<p>使用该方法，你甚至可以达到更高的FPS。此外，还向<code>Window</code>类中添加了一个全局标记，以启用或禁用截锥剔除。<code>GameItem</code>类也有启用或禁用过滤的标记，因为对于某些项，截锥剔除过滤可能没有意义。</p>
              
            </div>
          </div>
          <footer>
  
    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
        <a href="../26-cascaded-shadow-maps/" class="btn btn-neutral float-right" title="级联阴影映射">Next <span class="icon icon-circle-arrow-right"></span></a>
      
      
        <a href="../24-hud-revisited/" class="btn btn-neutral" title="回顾HUD - NanoVG"><span class="icon icon-circle-arrow-left"></span> Previous</a>
      
    </div>
  

  <hr/>

  <div role="contentinfo">
    <!-- Copyright etc -->
    
      <p>2019, Mouse0w0</p>
    
  </div>

  Built with <a href="https://www.mkdocs.org/">MkDocs</a> using a <a href="https://github.com/snide/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
      
        </div>
      </div>

    </section>

  </div>

  <div class="rst-versions" role="note" aria-label="versions">
    <span class="rst-current-version" data-toggle="rst-current-version">
      
          <a href="https://github.com/Mouse0w0/lwjglbook-CN-Translation/" class="fa fa-github" style="float: left; color: #fcfcfc"> GitHub</a>
      
      
        <span><a href="../24-hud-revisited/" style="color: #fcfcfc;">&laquo; Previous</a></span>
      
      
        <span style="margin-left: 15px"><a href="../26-cascaded-shadow-maps/" style="color: #fcfcfc">Next &raquo;</a></span>
      
    </span>
</div>
    <script>var base_url = '..';</script>
    <script src="../js/theme.js" defer></script>
      <script src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" defer></script>
      <script src="../search/main.js" defer></script>
    <script defer>
        window.onload = function () {
            SphinxRtdTheme.Navigation.enable(true);
        };
    </script>

</body>
</html>
